package com.zlk.algorithm.algorithm.dynamicPlan.longestIncreasingSubsequence;

import java.util.Arrays;

// 最长数对链
// 给你一个由n个数对组成的数对数组pairs
// 其中 pairs[i] = [lefti, righti] 且 lefti < righti
// 现在，我们定义一种 跟随 关系，当且仅当 b < c 时
// 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
// 我们用这种形式来构造 数对链
// 找出并返回能够形成的最长数对链的长度
// 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/
public class Code04_MaximumLengthOfPairChain {

    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        //主意要先排序，按照left 从小到大排序
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int[] ends = new int[n];
        int activeLen = 0;
        for (int i = 0; i < n; i++) {
            int index = findLeft(ends,activeLen,pairs[i][0]);
            if(index==-1){
                ends[activeLen++] = pairs[i][1];
            }else{
                //注意这个地方要比较
                ends[index] = Math.min(ends[index], pairs[i][1]);
            }
        }
        return activeLen;
    }

    public  int findLongestChain2(int[][] pairs) {
        int n = pairs.length;
        // 数对根据开始位置排序，从小到大
        // 结束位置无所谓！
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        // 结尾的数值
        int[] ends = new int[n];
        int len = 0;
        for (int[] pair : pairs) {
            int find = findLeft(ends, len, pair[0]);
            if (find == -1) {
                ends[len++] = pair[1];
            } else {
                ends[find] = Math.min(ends[find], pair[1]);
            }
        }
        return len;
    }

    private int findLeft(int[] ends, int activeLen, int num) {
        int l = 0;
        int r = activeLen-1;
        int mid = 0;
        int ans = -1;
        while (l<=r){
            mid = (l+r)/2;
            if(ends[mid]>=num){
                ans = mid;
                r = mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }




}
